import java.util.*;

/**
 * 课程表
 * https://leetcode.cn/problems/course-schedule/description/
 */
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1.准备工作，创建数组，容器，队列
        int[] cnt = new int[numCourses];
        Map<Integer,List<Integer>> map = new HashMap<>();

        Queue<Integer> q = new LinkedList<>();

        //2.建图
        for(int i = 0;i < prerequisites.length;i++){
            //获取课程
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            //判断是否已经存在
            if(!map.containsKey(b)){
                //创建容器
                map.put(b,new ArrayList<Integer>());
            }
            //添加指向
            map.get(b).add(a);
            //边+1
            cnt[a]++;
        }
        //3.拓扑排序
        //将所有度为0的节点加入队列
        for(int i = 0;i < numCourses;i++){
            if(cnt[i] == 0){
                q.offer(i);
            }
        }

        //出队列，删除边
        while(!q.isEmpty()){
            int x = q.poll();

            //将对应的边删除
            for(int t : map.getOrDefault(x,new ArrayList<Integer>())){
                cnt[t]--;
                //判断是否度为0
                if(cnt[t] == 0){
                    q.offer(t);
                }
            }
        }

        //4.判断是否有环
        for(int x : cnt) if(x != 0) return false;
        return true;
    }
}

class Solution1 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        //1.预处理阶段
        int cnt[] = new int[numCourses];
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        Queue<Integer> q = new LinkedList<>();

        int ret[] = new int[numCourses];
        int index = 0;

        //2.建图

        for(int i = 0;i < prerequisites.length;i++){
            int b = prerequisites[i][0];
            int a = prerequisites[i][1];

//            if(list.get(a) == null){
//               list.add(new LinkedList<>());
//            }

            list.get(a).add(b);
            cnt[b]++;
        }

        //3.拓扑排序
        //3.1度为0的节点加入
        for(int i = 0;i < numCourses;i++){
            if(cnt[i] == 0){
                q.offer(i);
            }
        }
        //3.2 出队列，加入度为0的节点
        while(!q.isEmpty()){
            int x = q.poll();

            ret[index++] = x;

            //消除边
            for(int t : list.get(x)){
                cnt[t]--;
                if(cnt[t] == 0){
                    q.offer(t);
                }
            }
        }

        //4.是否存环
        for(int tem : cnt) if(tem != 0) return new int[0];

        return ret;
    }

    public static void main(String[] args) {
        Solution1 s  = new Solution1();
        int[][] p = new int[][]{{1,0},{2,0},{3,1},{3,2}};
        int[] ret = s.findOrder(4,p);
        for(int x : ret) System.out.print(x + " ");
    }
}